Homework (Week 9)
Table of Contents
Submission: Due on Friday, 5th August, 11AM Sydney Time. Please submit using the CSE Give System either online or via this command on a CSE terminal:
give cs3151 hw8 hw8.pdf
Late submissions are accepted up to five days after the deadline, but at a penalty: 5% off your total mark per day.
This assignment uses Ben-Ari's DAJ tool, a visual aid for studying distributed algorithms, It is available for download at https://github.com/motib/daj.
Clone the repository, then run the tool by executing
java -jar daj.jar
1 The Byzantine Generals Algorithm (6 marks)
In the Byzantine Generals Algorithm, suppose that there is exactly 1 (one) traitor and that Ivan’s data structures are:
- Who is the traitor? Justify your answer (explain why this general is the traitor and why none of the other generals can be the traitor).
- What does Ivan decide about Basil’s and John’s plans? What does Ivan decide about the overall majority plan?
- Using DAJ, construct a minimal scenario leading to the shown data structure for Ivan. In this minimal scenario, the traitor's only incorrect messages should be the ones in Ivan's data structure above. Provide a screenshot of the main window in DAJ.
- For the scenario constructed in the previous question, provide screenshots of the 4 (four) knowledge trees that DAJ constructs about each of the generals. Note that knowledge trees are called "message trees" in DAJ. Which of these knowledge (message) trees indicate the traitor's incorrect messages?
2 The Dijkstra-Scholten Algorithm (4 marks)
A distributed system with 4 (four) nodes including 1 (one) environment node is depicted with the following directed graph:
Using DAJ, construct a scenario for each of the 4 (four) different spanning trees in the above directed graph. These scenarios differ in the order of the sent messages (but note that some orders of sent messages result in the same spanning tree, while you have to find all different spanning trees). For each of these scenarios, only provide a screenshot of the spanning tree that DAJ constructs.
3 Permissionless consensus (3 marks)
Bitcoin uses what's called proof-of-work consensus, where the first node to solve a computationally expensive puzzle gets to pick the next block.
How does Bitcoin mitigate the problem of two nodes solving the puzzle at roughly the same time, causing a split decision? Skim the Bitcoin white paper for the answer. Explain informally and in your own words.